{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最长连续序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestConsecutive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长连续序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个未排序的整数数组 <code>nums</code> ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [100,4,200,1,3,2]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长数字连续序列是 <code>[1, 2, 3, 4]。它的长度为 4。</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,3,7,2,5,8,4,6,0,1]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>可以设计并实现时间复杂度为&nbsp;<code>O(n)</code><em> </em>的解决方案吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 128&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/longest-consecutive-sequence/\">https://leetcode-cn.com/problems/longest-consecutive-sequence/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WhsWhI](https://leetcode.cn/problems/WhsWhI/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WhsWhI](https://leetcode.cn/problems/WhsWhI/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[100,4,200,1,3,2]', '[0,3,7,2,5,8,4,6,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 1\n",
    "        n = len(nums)\n",
    "        seq = 1\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                seq += 1\n",
    "            elif  nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                seq = 1\n",
    "            res = max(res, seq)\n",
    "        return res if nums else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        best=0\n",
    "        n=0\n",
    "        #print(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]-nums[i-1]==1:\n",
    "                #print(nums[i])\n",
    "                n+=1\n",
    "            elif nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                n=0\n",
    "            \n",
    "            if best<n:\n",
    "                best=n\n",
    "                #print(best)\n",
    "        if len(nums)>0:\n",
    "            best+=1\n",
    "\n",
    "        return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort()\n",
    "\n",
    "        res = [nums[0]]\n",
    "\n",
    "        length = 1\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i]==res[-1]+1:\n",
    "                res.append(nums[i])\n",
    "            elif nums[i]==res[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                res = [nums[i]]\n",
    "            length = max(length, len(res))\n",
    "\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        index, stack = 1, [nums[0]]\n",
    "        maximum, tmpmax = 1, 1\n",
    "        while index < len(nums):\n",
    "            if nums[index] == stack[-1]:\n",
    "                index += 1\n",
    "            elif nums[index] - 1 == stack[-1]:\n",
    "                tmpmax += 1\n",
    "                stack.append(nums[index])\n",
    "                index += 1\n",
    "            else:\n",
    "                tmpmax = 1\n",
    "                stack = [nums[index]]\n",
    "                index += 1\n",
    "            maximum = max(maximum, tmpmax)\n",
    "        return maximum\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        [100, 4, 200, 1, 3, 2],\n",
    "        [0, 3, 7, 2, 5, 8, 4, 6, 0, 1],\n",
    "        [0,1,1,2,3,4,5,7,8,9,10,11,12,12,13,14]\n",
    "    ]:\n",
    "        ret = s.longestConsecutive(testcase)\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: [int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        sorted_nums = sorted(nums)\n",
    "        res = min(1, len(sorted_nums))\n",
    "        tmp_len = 1\n",
    "        for idx in range(1, len(sorted_nums)):\n",
    "            if sorted_nums[idx] == sorted_nums[idx - 1] + 1:\n",
    "                tmp_len += 1\n",
    "            elif sorted_nums[idx] == sorted_nums[idx - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                res = max(res, tmp_len)\n",
    "                tmp_len = 1\n",
    "        return max(res, tmp_len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        count = 0\n",
    "        cur = 0\n",
    "        for i in range(len(nums)):\n",
    "            if cur > 0:\n",
    "                if nums[i] == curval + 1:\n",
    "                    curval = nums[i]\n",
    "                    cur += 1\n",
    "                elif nums[i] == curval:\n",
    "                    continue\n",
    "                else:\n",
    "                    count = max(count, cur)\n",
    "                    cur = 0\n",
    "\n",
    "            if cur == 0:\n",
    "                curval = nums[i]\n",
    "                cur += 1\n",
    "            \n",
    "        return max(count, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        ans = 0\n",
    "        if len(nums)==0:\n",
    "            res = 0\n",
    "        else :res = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]+1 == nums[i+1]:\n",
    "                res+=1\n",
    "            elif nums[i] == nums[i+1]:\n",
    "                continue\n",
    "            else:\n",
    "                ans = max(ans,res)\n",
    "                res = 1\n",
    "        return max(ans,res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        size=len(nums)\n",
    "        if size<2:\n",
    "            return size\n",
    "        print(nums)\n",
    "        cnt=res=1\n",
    "        for i in range(1,size):\n",
    "            if nums[i]-nums[i-1]==1:\n",
    "                cnt+=1\n",
    "            if nums[i]-nums[i-1]>1 or i==size-1:\n",
    "                res=max(res,cnt)\n",
    "                cnt=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        result = 1\n",
    "        starts = {}\n",
    "        ends = {}\n",
    "        for num in nums:\n",
    "            if num in starts or num in ends:\n",
    "                continue\n",
    "            lLength = ends.get(num - 1, 0)\n",
    "            rLength = starts.get(num + 1, 0)\n",
    "            newLength = lLength + rLength + 1\n",
    "            ends[num + rLength] = newLength\n",
    "            starts[num - lLength] = newLength\n",
    "            ends.pop(num - 1, None)\n",
    "            starts.pop(num + 1, None)\n",
    "            result = max(result, newLength)\n",
    "        return result\n",
    "                \n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        def quickSort(group: list):\n",
    "            size = len(group)\n",
    "            if size == 1:\n",
    "                return group\n",
    "\n",
    "            pivot = choice(range(size))\n",
    "            left, right = [], []\n",
    "\n",
    "            i= 0\n",
    "            while i < size:\n",
    "                if i == pivot:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if group[i] < group[pivot]:\n",
    "                    left.append(group[i])\n",
    "                elif group[i] > group[pivot]:\n",
    "                    right.append(group[i])\n",
    "                i += 1\n",
    "\n",
    "            if left:\n",
    "                left = quickSort(left)\n",
    "            if right:\n",
    "                right = quickSort(right)\n",
    "\n",
    "            left.append(group[pivot])\n",
    "            left.extend(right)\n",
    "\n",
    "            return left\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        nums = quickSort(nums)\n",
    "        nums.append(float('-inf'))\n",
    "\n",
    "        i, size, head, maxln = 1, len(nums), 0, 1\n",
    "        while i < size:\n",
    "            if nums[i] - nums[i-1] != 1:\n",
    "                maxln = max(maxln, i-head)\n",
    "                head = i\n",
    "\n",
    "                if maxln >= size-i+1:\n",
    "                    return maxln\n",
    "            i += 1\n",
    "\n",
    "        return maxln"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        print(nums)\n",
    "        dp = [1] * len(nums)\n",
    "        ret = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            ret = max(ret, dp[i])\n",
    "        print(dp)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # if not nums: return 0\n",
    "        # if len(nums)==1: return 1\n",
    "\n",
    "        # nums = sorted(list(set(nums)))\n",
    "        # left = 0\n",
    "        # right = 1\n",
    "        # n = len(nums)\n",
    "        # max_len = 0\n",
    "        # while right < n:\n",
    "        #     print(right,left)\n",
    "        #     if nums[right] - nums[right-1] == 1:\n",
    "        #         right +=1\n",
    "        #     else:\n",
    "        #         max_len = max(max_len,right-1)\n",
    "        #         left = right \n",
    "        #         right = right + 1 \n",
    "        # if left < right:\n",
    "        #     max_len = max(max_len,right-1)\n",
    "        # return max_len\n",
    "\n",
    "        # ### 动态规划\n",
    "        if not nums: return 0\n",
    "        if len(nums)==1: return 1\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i - 1] + 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "                ans = max(ans, dp[i])\n",
    "            elif nums[i] == nums[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # if not nums: return 0\n",
    "        # if len(nums)==1: return 1\n",
    "\n",
    "        # nums = sorted(list(set(nums)))\n",
    "        # left = 0\n",
    "        # right = 1\n",
    "        # n = len(nums)\n",
    "        # max_len = 0\n",
    "        # while right < n:\n",
    "        #     print(right,left)\n",
    "        #     if nums[right] - nums[right-1] == 1:\n",
    "        #         right +=1\n",
    "        #     else:\n",
    "        #         max_len = max(max_len,right-1)\n",
    "        #         left = right \n",
    "        #         right = right + 1 \n",
    "        # if left < right:\n",
    "        #     max_len = max(max_len,right-1)\n",
    "        # return max_len\n",
    "\n",
    "        # ### 动态规划\n",
    "        if not nums: return 0\n",
    "        if len(nums)==1: return 1\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i - 1] + 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "                ans = max(ans, dp[i])\n",
    "            elif nums[i] == nums[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 如果用并查集 排序后 对每个数n 判断n+1在不在nums中 如果在就可以union(n, n+1)\n",
    "        # 构建完并查集后 如何求最大的长度呢 不能再对每个节点利用visit做bfs吧 这样复杂度也太高了\n",
    "\n",
    "        # 枚举 + 剪枝\n",
    "        # nums = sorted(nums)\n",
    "        # res = 0\n",
    "        # s = -inf\n",
    "        # for e in nums:\n",
    "        #     if e < s:\n",
    "        #         continue\n",
    "        #     s = e+1\n",
    "        #     length = 1\n",
    "        #     while s in nums:\n",
    "        #         s += 1\n",
    "        #         length += 1\n",
    "        #     res = max(res, length)\n",
    "        # return res\n",
    "\n",
    "        # 排序 + 双指针遍历所有连续序列 + 去重优化\n",
    "        # if not nums:\n",
    "        #     return 0\n",
    "        # nums = sorted(nums)\n",
    "        # j = 1\n",
    "        # res = 1\n",
    "        # cur = 1\n",
    "        # while j < len(nums):\n",
    "        #     # 连续数组\n",
    "        #     if nums[j-1] + 1 == nums[j]:\n",
    "        #         cur += 1\n",
    "        #         j += 1\n",
    "        #     # 重复元素\n",
    "        #     elif nums[j-1] == nums[j]:\n",
    "        #         j += 1\n",
    "        #         pass\n",
    "        #     # 间断\n",
    "        #     elif nums[j-1] + 1 != nums[j]:\n",
    "        #         # 新开一组ij\n",
    "        #         res = max(res, cur)\n",
    "        #         cur = 1\n",
    "        #         j += 1\n",
    "        # # 注意还剩一个j遍历到最后跳出的情况没比较\n",
    "        # res = max(res, cur)\n",
    "        # return res\n",
    "\n",
    "        # dp\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        dp = [1 for _ in range(len(nums))]\n",
    "        res = 1\n",
    "        for i in range(1, len(dp)):\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            res = max(dp[i], res)\n",
    "        return res\n",
    "\n",
    "        # 比较重要的思路是并查集\n",
    "        # 每个连续序列的起始值i 不存在i-1\n",
    "        # 非起始值i 存在i-1  并且序列长度可以在创建的过程中比较\n",
    "        \n",
    "        # def find(x):\n",
    "        #     if nums[x] == x:\n",
    "        #         return x\n",
    "        #     else:\n",
    "        #         return find(nums[x])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if nums==[]: return 0\n",
    "        nums.sort()\n",
    "\n",
    "        dp=[]\n",
    "\n",
    "        for i in range(len(nums)):   \n",
    "            dp.append(1)\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "            \n",
    "            elif i>0 and nums[i]-nums[i-1]==1:\n",
    "                dp[i]=dp[i-1]+1\n",
    "        \n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        if n == 0: return res\n",
    "        dp = [1] * n\n",
    "        res = 1\n",
    "        nums.sort()\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i - 1] + 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "                res = max(res, dp[i])\n",
    "            elif nums[i] == nums[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        nums.sort()\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        num_set = set(nums)\n",
    "        for num in num_set:\n",
    "            if num-1 not in num_set:\n",
    "                cur = num\n",
    "                cur_res = 1\n",
    "                while(cur+1 in num_set):\n",
    "                    cur = cur+1\n",
    "                    cur_res += 1\n",
    "                res = max(cur_res, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return n\n",
    "\n",
    "        nums=sorted(nums)\n",
    "        dp=[1 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]+1:\n",
    "                dp[i]+=dp[i-1]\n",
    "            if nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        dp = [1 for _ in range(len(nums))]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i-1]+1==nums[i]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            elif nums[i-1]==nums[i]:\n",
    "                dp[i]=dp[i-1]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        dp = [1] * len(nums)\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        result = 1\n",
    "        # nums = set(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - nums[i-1] == 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            result = max(result, dp[i])\n",
    "        return result\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if i - 1 not in nums:\n",
    "                ans = max(ans, len(list(takewhile(lambda x: x in nums, count(i)))))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = sorted(list(set(nums)))\n",
    "        used = set()\n",
    "        mm = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            temp = 1\n",
    "            count = 1\n",
    "            if num in used:\n",
    "                continue\n",
    "            used.add(num)\n",
    "            for n in nums[i:]:\n",
    "                if n == num + count:\n",
    "                    used.add(n)\n",
    "                    count +=1\n",
    "                    temp += 1\n",
    "            mm = max(mm,temp)\n",
    "        return mm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        seen = {}\n",
    "        for num in nums:\n",
    "            seen[num] = False\n",
    "        \n",
    "        maxLength = 0\n",
    "        for num in nums:\n",
    "\n",
    "            if seen[num] == True:\n",
    "                continue\n",
    "            # track back to the smallest number of the series\n",
    "            while num - 1 in seen:\n",
    "                num = num - 1\n",
    "\n",
    "            length = 0\n",
    "            while num in seen:\n",
    "                length += 1\n",
    "                seen[num] = True\n",
    "                num = num + 1\n",
    "            maxLength = max(maxLength, length)\n",
    "\n",
    "        return maxLength\n",
    "             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        max_value=0\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if i-1==0:\n",
    "                dp[i]=1\n",
    "            else:\n",
    "                if nums[i-1]-nums[i-2]==1:\n",
    "                    dp[i]=dp[i-1]+1\n",
    "                elif nums[i-1]-nums[i-2]==0:\n",
    "                    dp[i]=dp[i-1]\n",
    "                else:\n",
    "                    dp[i]=1\n",
    "            max_value=max(max_value,dp[i])\n",
    "        print(dp)\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i - 1] + 1:\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, cur)\n",
    "                cur = 1\n",
    "\n",
    "        return max(ans, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        res = 1\n",
    "        tmp = 1\n",
    "        for inx in range(1, len(nums)):\n",
    "            print(inx, nums[inx], nums[inx - 1] + 1)\n",
    "            if nums[inx] != nums[inx - 1] + 1:\n",
    "                tmp = 1\n",
    "            else:\n",
    "                tmp += 1\n",
    "            res = max(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 如果用并查集 排序后 对每个数n 判断n+1在不在nums中 如果在就可以union(n, n+1)\n",
    "        # 构建完并查集后 如何求最大的长度呢 不能再对每个节点利用visit做bfs吧 这样复杂度也太高了\n",
    "\n",
    "        # 枚举 + 剪枝\n",
    "        nums_t = sorted(nums)\n",
    "        nums = set(nums_t)\n",
    "        res = 0\n",
    "        s = -inf\n",
    "        for e in nums_t:\n",
    "            if e < s:\n",
    "                continue\n",
    "            s = e+1\n",
    "            length = 1\n",
    "            while s in nums:\n",
    "                s += 1\n",
    "                length += 1\n",
    "            res = max(res, length)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        nums=list(set(nums))   \n",
    "        nums.sort()\n",
    "        maxlen=1\n",
    "        start=0\n",
    "        for end in range(1,len(nums)):\n",
    "            if nums[end]-nums[end-1] ==1:\n",
    "                maxlen=max(maxlen,end-start+1)\n",
    "            else:\n",
    "                start=end\n",
    "                \n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        \n",
    "        res, s = 0, set(nums)\n",
    "        for num in nums:\n",
    "            if num -1 not in s:\n",
    "                t = 1\n",
    "                next = num + 1\n",
    "                while next in s:\n",
    "                    t += 1\n",
    "                    next += 1\n",
    "                res = max(res, t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        longest_streak = 0\n",
    "        num_set = set(nums)\n",
    "\n",
    "        for num in num_set:\n",
    "            if num - 1 not in num_set:\n",
    "                current_num = num\n",
    "                current_streak = 1\n",
    "\n",
    "                while current_num + 1 in num_set:\n",
    "                    current_num += 1\n",
    "                    current_streak += 1\n",
    "\n",
    "                longest_streak = max(longest_streak, current_streak)\n",
    "\n",
    "        return longest_streak\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        numSet = set(nums)\n",
    "        long = 0\n",
    "\n",
    "        for num in numSet:\n",
    "            if num - 1 not in numSet:\n",
    "                currentNum = num\n",
    "                current = 1\n",
    "                while currentNum + 1 in numSet:\n",
    "                    currentNum += 1\n",
    "                    current += 1\n",
    "                long = max(long, current)\n",
    "\n",
    "        return long"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        nums = list(set(nums))\n",
    "        nums = sorted(nums)\n",
    "        max_l = 1\n",
    "        tmp_l = 1\n",
    "        print(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1]+1:\n",
    "                tmp_l += 1\n",
    "                max_l = max(max_l, tmp_l)\n",
    "            else:\n",
    "                tmp_l = 1\n",
    "            print(tmp_l)\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums=list(set(nums))\n",
    "        if len(nums)<2:return len(nums)\n",
    "        nums.sort()\n",
    "        res,ans=set(),1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1]-nums[i]==1:\n",
    "                res.add(nums[i])\n",
    "                res.add(nums[i+1])\n",
    "            else:ans,res=max(ans,len(res)),set()\n",
    "        return max(ans,len(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestConsecutive(self, nums):\n",
    "        hash_dict = dict()\n",
    "        \n",
    "        max_length = 0\n",
    "        for num in nums:\n",
    "            if num not in hash_dict:\n",
    "                left = hash_dict.get(num - 1, 0)\n",
    "                right = hash_dict.get(num + 1, 0)\n",
    "                \n",
    "                cur_length = 1 + left + right\n",
    "                if cur_length > max_length:\n",
    "                    max_length = cur_length\n",
    "                \n",
    "                hash_dict[num] = cur_length\n",
    "                hash_dict[num - left] = cur_length\n",
    "                hash_dict[num + right] = cur_length\n",
    "                \n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        union_query_map = {}\n",
    "\n",
    "        for n in nums:\n",
    "            if n in union_query_map:\n",
    "                continue\n",
    "            left = n - 1\n",
    "            right = n + 1\n",
    "            left_length = union_query_map.get(left, 0)\n",
    "            right_length = union_query_map.get(right, 0)\n",
    "\n",
    "            union_query_map[n] = 1 + left_length + right_length\n",
    "            union_query_map[n - left_length] = 1 + left_length + right_length\n",
    "            union_query_map[n + right_length] = 1 + left_length + right_length\n",
    "\n",
    "            ans = max(ans, 1 + left_length + right_length)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        pre_dict = {}\n",
    "        for n in nums:\n",
    "            pre_dict[n] = 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in pre_dict:\n",
    "            if i - 1 not in pre_dict:\n",
    "                y = i + 1\n",
    "                while y in pre_dict:\n",
    "                    y += 1\n",
    "                res = max(res, y - i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        dicts = {}\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            dicts[x] = 1\n",
    "        for x in nums:\n",
    "            if dicts[x] == 1:\n",
    "                temp = x\n",
    "                while dicts.get(temp, 0) == 1:\n",
    "                    temp -= 1\n",
    "                if dicts.get(temp, 0) != 0:\n",
    "                    dicts[x] += dicts[temp]\n",
    "\n",
    "                dicts[x] += x - temp - 1\n",
    "            ans = max(ans, dicts[x])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        f = {}\n",
    "        for num in nums:\n",
    "            if num not in f:\n",
    "                f[num] = self.get_father(f, num)\n",
    "        max_len = 1\n",
    "        for num in nums:\n",
    "            max_len = max(max_len, num - self.get_father(f, num) + 1)\n",
    "        return max_len\n",
    "\n",
    "    def get_father(self, f: Dict[int, int], x: int) -> int:\n",
    "        nodes = []\n",
    "        while (x - 1) in f:\n",
    "            nodes.append(x)\n",
    "            x = min(x - 1, f[x - 1])\n",
    "        for node in nodes:\n",
    "            f[node] = x\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        # 存储每个数字可以组成的最长序列\n",
    "        dict_ = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dict_:\n",
    "                right_length = dict_.get(nums[i]+1, 0)\n",
    "                left_length = dict_.get(nums[i]-1, 0)\n",
    "                cur_length = right_length + left_length + 1\n",
    "                dict_[nums[i]-left_length] = cur_length\n",
    "                dict_[nums[i]+right_length] = cur_length\n",
    "                dict_[nums[i]] = cur_length\n",
    "        return max(dict_.values())\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        self.len = len(nums)\n",
    "        if self.len<2:\n",
    "            return self.len\n",
    "        self.set = set()\n",
    "        for num in nums:\n",
    "            self.set.add(num)\n",
    "        res = 1\n",
    "        for item in self.set.copy():\n",
    "            res = max(res, self.bfs(item, nums))\n",
    "        return (res)\n",
    "\n",
    "    def bfs(self, num, nums):\n",
    "        queue = []\n",
    "        queue.append(num)\n",
    "        self.set.discard(num)\n",
    "        res = 1\n",
    "        while len(queue)>0:\n",
    "            cur = queue.pop(0)\n",
    "            if cur+1 in self.set:\n",
    "                queue.append(cur+1)\n",
    "                self.set.discard(cur+1)\n",
    "                res+=1\n",
    "            if cur-1 in self.set:\n",
    "                queue.append(cur-1)\n",
    "                self.set.discard(cur-1)\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 广度优先搜素\n",
    "        def dfs(num):\n",
    "            que = deque()\n",
    "            que.append(num)\n",
    "            dic.pop(num)\n",
    "            length = 1\n",
    "            while que:\n",
    "                cur = que.popleft()\n",
    "                neighbor = [cur - 1, cur + 1]\n",
    "                for nei in neighbor:\n",
    "                    if nei in dic:\n",
    "                        que.append(nei)\n",
    "                        dic.pop(nei)\n",
    "                        length += 1\n",
    "            return length\n",
    "        \n",
    "        dic = Counter(nums)\n",
    "        dic2 = dic.copy()\n",
    "        longest = 0\n",
    "        while dic:\n",
    "            for num in dic2:\n",
    "                if num in dic:\n",
    "                    longest = max(longest,dfs(num))\n",
    "        return longest\n",
    "        # 并查集\n",
    "        # def findfather(ind):\n",
    "        #     if fathers[ind] != ind:\n",
    "        #         fathers[ind] = findfather(fathers[ind])\n",
    "        #     return fathers[ind]\n",
    "        \n",
    "        # def union(num1,num2):\n",
    "        #     fathernum1 = findfather(num1)\n",
    "        #     fathernum2 = findfather(num2)\n",
    "        #     if fathernum1 != fathernum2:\n",
    "        #         fathers[fathernum1] = fathernum2\n",
    "\n",
    "        #         count1 = counts[fathernum1]\n",
    "        #         count2 = counts[fathernum2]\n",
    "        #         counts[fathernum2] = count1 + count2\n",
    "\n",
    "        # fathers, counts, dic = dict(), dict(), dict()\n",
    "        \n",
    "        # for i in range(len(nums)):\n",
    "        #     fathers[nums[i]] = nums[i]\n",
    "        #     counts[nums[i]] = 1\n",
    "        #     dic[nums[i]] = 0\n",
    "        \n",
    "        # for num in nums:\n",
    "        #     if (num + 1) in dic:\n",
    "        #         union(num,num + 1)\n",
    "        #     if (num - 1) in dic:\n",
    "        #         union(num - 1, num)\n",
    "            \n",
    "        # longest = 0\n",
    "        # for val in counts.values():\n",
    "        #     longest = max(longest, val)\n",
    "        # return longest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        num2index = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in num2index:\n",
    "                num2index[num] = i\n",
    "        max_l = 0\n",
    "        dp = [0] * len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            if dp[i] == 0:\n",
    "                dp[i] = 1\n",
    "                curr = 1\n",
    "                curr_num = num\n",
    "                while curr_num+1 in num2index:\n",
    "                    dp[num2index[curr_num+1]] = 1\n",
    "                    curr += 1\n",
    "                    curr_num += 1\n",
    "                max_l = max(max_l, curr)\n",
    "        return max_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        hashmap = Counter()\n",
    "        for i in nums:\n",
    "            hashmap[i] = 1\n",
    "        keys = list(hashmap.keys())\n",
    "        keys.sort()\n",
    "        for i in keys:\n",
    "            hashmap[i] = hashmap[i-1]+1\n",
    "            \n",
    "        return max(list(hashmap.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        parent = {}\n",
    "        def find(index):\n",
    "            if index != parent[index]:\n",
    "                return find(parent[index])\n",
    "            return parent[index]\n",
    "        for i in nums:\n",
    "            parent[i] = i\n",
    "            if (i + 1) in parent:\n",
    "                parent[i] = find(i + 1)\n",
    "            if (i - 1) in parent:\n",
    "                parent[i - 1] = parent[i]\n",
    "        res = 1\n",
    "        for i in parent:\n",
    "            res = max(res, find(parent[i]) - i + 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        parent = {}\n",
    "        def find(index):\n",
    "            if index != parent[index]:\n",
    "                return find(parent[index])\n",
    "            return parent[index]\n",
    "        for i in nums:\n",
    "            parent[i] = i\n",
    "            if (i + 1) in parent:\n",
    "                parent[i] = find(i + 1)\n",
    "            if (i - 1) in parent:\n",
    "                parent[i - 1] = find(parent[i])\n",
    "        res = 1\n",
    "        for i in parent:\n",
    "            res = max(res, find(parent[i]) - i + 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        set_nums = set(nums)\n",
    "        dict_n_len = {}\n",
    "        find_num = set()\n",
    "        max_len = 0\n",
    "        for n in nums:\n",
    "            # 如果这个元素已经查找过，则它被包含在其他的序列中，继续\n",
    "            if n in find_num:\n",
    "                continue\n",
    "            # 将这元素作为起点\n",
    "            find_num.add(n)\n",
    "            dict_n_len[n] = 1\n",
    "\n",
    "            # 看这个序列能走多远\n",
    "            next_n = n + 1\n",
    "            while next_n in set_nums:\n",
    "                # 当发现下一个元素在已经走过的起点\n",
    "                if next_n in dict_n_len:\n",
    "                    dict_n_len[n] += dict_n_len[next_n]\n",
    "                    break\n",
    "                \n",
    "                find_num.add(next_n)\n",
    "                dict_n_len[n] += 1\n",
    "                next_n += 1\n",
    "            if dict_n_len[n] > max_len:\n",
    "                max_len = dict_n_len[n]\n",
    "        \n",
    "        return max_len\n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nset = set(nums)\n",
    "        cache = {}\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x-1 not in cache:\n",
    "                cache[x] = 1\n",
    "                i = 1\n",
    "                while x+i in nset:\n",
    "                    if x+i in cache:\n",
    "                        cache[x] += cache[x+i]\n",
    "                        break\n",
    "                    cache[x] += 1\n",
    "                    i += 1\n",
    "                res = max(res, cache[x])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 原数组没有排序，排序后可以用双指针方法\n",
    "        # 由于存在重复元素，所以直接排序可能会出现问题\n",
    "        nums = sorted(collections.Counter(nums).items())\n",
    "        # print(nums)\n",
    "        start,end = 0,1\n",
    "        n = len(nums)\n",
    "        if n<=1:\n",
    "            return n\n",
    "        max_length = 1\n",
    "        while end<n:\n",
    "            if nums[end][0]==nums[end-1][0]+1:\n",
    "                end+=1\n",
    "                max_length = max(max_length,end-start)\n",
    "            else:\n",
    "                start = end\n",
    "                end += 1\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "\n",
    "        dic = {}\n",
    "        nums.sort()\n",
    "        for  i,x in enumerate(nums):\n",
    "\n",
    "            if x-1 in dic:\n",
    "                dic[x]=dic[x-1]+1\n",
    "            else:\n",
    "                if x not in dic:\n",
    "                    dic[x]=1\n",
    "        \n",
    "        print(dic)\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        return max(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        cnts = Counter()\n",
    "        for x in sorted(nums):\n",
    "            cnts[x] = cnts[x-1] + 1\n",
    "        return max(list(cnts.values()) + [0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "\n",
    "        index = { x:i for i,x in enumerate(nums) }\n",
    "\n",
    "        n = len(nums)\n",
    "        maxlength = 0\n",
    "        visited = set()\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in visited: continue\n",
    "            a = nums[i]\n",
    "            visited.add(index[a])\n",
    "            length = 1\n",
    "            while a + 1 in index:\n",
    "                a = a + 1\n",
    "                visited.add(index[a])\n",
    "                length += 1\n",
    "            maxlength = max(maxlength, length)\n",
    "\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        max_val = 0\n",
    "        for item in nums:\n",
    "            if item in dic:\n",
    "                continue\n",
    "            left_most, right_most = item, item\n",
    "            if item + 1 in dic:\n",
    "                right_most = dic[item+1][1]\n",
    "            if item - 1 in dic:\n",
    "                left_most = dic[item-1][0]\n",
    "            dic[left_most] = (left_most, right_most)\n",
    "            dic[right_most] = (left_most, right_most)\n",
    "            dic[item] = (left_most, right_most)\n",
    "            if max_val < (right_most-left_most+1):\n",
    "                max_val = (right_most-left_most+1)\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        st = {}\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        for n in nums:\n",
    "            if n not in dic:\n",
    "                dic[n] = 1\n",
    "                st[n] = 0\n",
    "        res = 1\n",
    "        for key in dic:\n",
    "            if st[key] == 1:\n",
    "                continue\n",
    "            st[key] = 1\n",
    "            if key-1 in dic and key+1 in dic:\n",
    "                tmp = key - 1\n",
    "                length = 1\n",
    "                while tmp in dic:\n",
    "                    length += 1\n",
    "                    st[tmp] = 1\n",
    "                    tmp -= 1\n",
    "                tmp = key + 1\n",
    "                while tmp in dic:\n",
    "                    length += 1\n",
    "                    st[tmp] = 1\n",
    "                    tmp += 1\n",
    "                res = max(res,length)\n",
    "            elif key-1 in dic:\n",
    "                tmp = key - 1\n",
    "                length = 1\n",
    "                while tmp in dic:\n",
    "                    length += 1\n",
    "                    st[tmp] = 1\n",
    "                    tmp -= 1\n",
    "                res = max(res,length)\n",
    "            elif key+1 in dic:\n",
    "                tmp = key + 1\n",
    "                length = 1\n",
    "                while tmp in dic:\n",
    "                    length += 1\n",
    "                    st[tmp] = 1\n",
    "                    tmp += 1\n",
    "                res = max(res,length)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        p = {}\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        \n",
    "        def union(a, b):\n",
    "            p[find(b)] = find(a)\n",
    "\n",
    "        for n in nums:\n",
    "            if n in p:\n",
    "                continue\n",
    "            p[n] = n\n",
    "            if n-1 in p:\n",
    "                union(n-1, n)\n",
    "            if n+1 in p:\n",
    "                union(n, n+1)\n",
    "        \n",
    "        count = defaultdict(int)\n",
    "        ans = 0\n",
    "        for k in p.keys():\n",
    "            pk = find(k)\n",
    "            count[pk] += 1\n",
    "            ans = max(ans, count[pk])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        visit = set()\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[nums[i]] = dic.get(nums[i],0)\n",
    "        for i in range(n):\n",
    "            if nums[i] not in visit:\n",
    "                j = 1\n",
    "                while nums[i]-j in dic:\n",
    "                    visit.add(nums[i]-j)\n",
    "                    j += 1\n",
    "                dic[nums[i]] = j+dic[nums[i]-j+1]-1\n",
    "        #print(dic)\n",
    "        #print(visit)\n",
    "        return max(list(dic.values()))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        s = set( nums )\n",
    "        v = set( ) \n",
    "        dic = { }\n",
    "        for  j in s:\n",
    "            if j not in v:\n",
    "                k = j \n",
    "                dic[k] = 1 \n",
    "                while 1 :\n",
    "                    j+=1 \n",
    "                    if j  in dic:\n",
    "                        dic[k]+= dic[j]\n",
    "                        break \n",
    "                    elif j in s :\n",
    "                        v.add( j ) \n",
    "                        dic[k] += 1 \n",
    "                    else:\n",
    "                        break \n",
    "        return max( dic.values( ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, nums):\n",
    "        self.parent = {i:i for i in nums}\n",
    "        self.cnt = {i:1 for i in nums}\n",
    "\n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            x = self.parent[self.parent[x]]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        if y not in self.parent:\n",
    "            return 1\n",
    "\n",
    "        root1, root2 = self.find(x), self.find(y)\n",
    "        if root1 == root2:\n",
    "            return self.cnt[root1]\n",
    "        \n",
    "        self.parent[root2] = root1\n",
    "        self.cnt[root1] += self.cnt[root2]\n",
    "\n",
    "        return self.cnt[root1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if nums == []: return 0\n",
    "        nums = list(set(nums))\n",
    "        len_nums = len(nums)\n",
    "\n",
    "        dsu = DSU(nums)\n",
    "        max_len = 1\n",
    "\n",
    "        for num in nums:\n",
    "            max_len = max(max_len, dsu.union(num, num+1))\n",
    "\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        nums = sorted(list(set(nums)))\n",
    "        mp = dict()\n",
    "        res = 1\n",
    "        for i in nums:\n",
    "            if i - 1 in mp:\n",
    "                mp[i] = mp[i - 1] + 1\n",
    "                res = max(res, mp[i])\n",
    "            else:\n",
    "                mp[i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self._parent = list(range(n))\n",
    "        self._size = [1] * n\n",
    "        self._mx_size = int(n > 0)\n",
    "    \n",
    "    def query(self, v: int) -> int:\n",
    "        if self._parent[v] != v:\n",
    "            self._parent[v] = self.query(self._parent[v])\n",
    "        return self._parent[v]\n",
    "    \n",
    "    def union(self, a: int, b: int):\n",
    "        a_k, b_k = self.query(a), self.query(b)\n",
    "        if a_k == b_k:\n",
    "            return\n",
    "        if self._size[a_k] < self._size[b_k]:\n",
    "            self._parent[a_k] = b_k\n",
    "            self._size[b_k] += self._size[a_k]\n",
    "            self._mx_size = max(self._mx_size, self._size[b_k])\n",
    "        else:\n",
    "            self._parent[b_k] = a_k\n",
    "            self._size[a_k] += self._size[b_k]\n",
    "            self._mx_size = max(self._mx_size, self._size[a_k])\n",
    "    \n",
    "    def getMaxSize(self):\n",
    "        return self._mx_size\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(len(nums))\n",
    "        numToIdx = dict()\n",
    "        for i, n in enumerate(nums):\n",
    "            if n in numToIdx:\n",
    "                continue\n",
    "            numToIdx[n] = i\n",
    "            if n - 1 in numToIdx:\n",
    "                uf.union(i, numToIdx[n - 1])\n",
    "            if n + 1 in numToIdx:\n",
    "                uf.union(i, numToIdx[n + 1])\n",
    "        return uf.getMaxSize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.union_find = dict()\n",
    "        self.union_num = dict()\n",
    "\n",
    "    def inset(self, num):\n",
    "        self.union_find[num] = num\n",
    "        self.union_num[num] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        while self.union_find[x] != x:\n",
    "            x = self.union_find[x]\n",
    "        return x\n",
    "\n",
    "    def merge(self, x: int, y: int) -> int:\n",
    "        x1 = self.find(x)\n",
    "        y1 = self.find(y)\n",
    "        if x1 != y1:\n",
    "            self.union_find[y1] = x1\n",
    "            self.union_num[x1] = self.union_num[x1] + self.union_num[y1]\n",
    "\n",
    "        return self.union_num[x1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        record = UnionFind()\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for num in nums:\n",
    "            if num not in record.union_find:\n",
    "                record.inset(num)\n",
    "\n",
    "            if num - 1 in record.union_find:\n",
    "                res = max(res, record.merge(num, num - 1))\n",
    "\n",
    "            if num + 1 in record.union_find:\n",
    "                res = max(res, record.merge(num, num + 1))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.union_find = dict()\n",
    "        self.union_num = dict()\n",
    "\n",
    "    def inset(self, num):\n",
    "        self.union_find[num] = num\n",
    "        self.union_num[num] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        while self.union_find[x] != x:\n",
    "            self.union_find[x] = self.union_find[self.union_find[x]]\n",
    "            x = self.union_find[x]\n",
    "        return x\n",
    "\n",
    "    def merge(self, x: int, y: int) -> int:\n",
    "        x1 = self.find(x)\n",
    "        y1 = self.find(y)\n",
    "        if x1 != y1:\n",
    "            self.union_find[y1] = x1\n",
    "            self.union_num[x1] = self.union_num[x1] + self.union_num[y1]\n",
    "\n",
    "        return self.union_num[x1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        record = UnionFind()\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for num in nums:\n",
    "            if num not in record.union_find:\n",
    "                record.inset(num)\n",
    "\n",
    "            if num - 1 in record.union_find:\n",
    "                res = max(res, record.merge(num, num - 1))\n",
    "\n",
    "            if num + 1 in record.union_find:\n",
    "                res = max(res, record.merge(num, num + 1))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        hashmap = set(nums)\n",
    "        seen = set()\n",
    "        n = len(nums)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):    \n",
    "            if nums[i] not in seen:\n",
    "                start = nums[i]\n",
    "                cnt = 1\n",
    "                seen.add(start)\n",
    "\n",
    "                while start + 1 in hashmap:\n",
    "                    start += 1\n",
    "                    cnt += 1\n",
    "                    seen.add(start + 1)\n",
    "                ans = max(ans, cnt)\n",
    "\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    \"\"\"\n",
    "    并查集\n",
    "    \"\"\"\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.set_count = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find_set(self, i: int) -> int:\n",
    "        p = self.parent[i]\n",
    "        if i != p != self.parent[p]:\n",
    "            p = self.parent[i] = self.parent[p] = self.find_set(self.parent[p])\n",
    "        return p\n",
    "\n",
    "    def merge(self, i: int, j: int) -> bool:\n",
    "        i, j = self.find_set(i), self.find_set(j)\n",
    "        if i != j:\n",
    "            if self.size[i] < self.size[j]:\n",
    "                i, j = j, i\n",
    "            self.parent[j] = i\n",
    "            self.set_count -= 1\n",
    "            self.size[i] += self.size[j]\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def count_set(self) -> int:\n",
    "        return self.set_count\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        import collections\n",
    "        sets = collections.defaultdict(set)\n",
    "        for i in range(len(self.parent)):\n",
    "            sets[self.find_set(i)].add(i)\n",
    "        return str(list(sets.values()))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        ufs = UnionFindSet(n)\n",
    "        d = {}\n",
    "        for (i, x) in enumerate(nums):\n",
    "            if x - 1 in d:\n",
    "                ufs.merge(d[x - 1], i)\n",
    "            if x + 1 in d:\n",
    "                ufs.merge(d[x + 1], i)\n",
    "            d[x] = i\n",
    "        return max(Counter((ufs.find_set(i) for i in range(n))).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if nums==[]:\n",
    "            return 0\n",
    "        dic = {}\n",
    "        count = {}\n",
    "        for i in nums:\n",
    "            dic[i] = i\n",
    "            count[i] = 1\n",
    "        def f(x):\n",
    "            if dic[x] == x:\n",
    "                return x\n",
    "            else:\n",
    "                dic[x] = f(dic[x])\n",
    "                return dic[x]\n",
    "        for i in nums:\n",
    "            if i+1 in dic:\n",
    "                dic[i+1] = i\n",
    "                count[i] += count[i+1]\n",
    "                count[i+1] = 0\n",
    "                # print(count)\n",
    "            if i-1 in dic:\n",
    "                dic[i] = f(i-1)\n",
    "                count[dic[i]] += count[i]\n",
    "                count[i] = 0\n",
    "                # print(count)\n",
    "        return max(count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        maxlen = 0\n",
    "        for x in nums:\n",
    "            if x in d:\n",
    "                continue\n",
    "            l, r = x, x\n",
    "            d[x] = [x, x]\n",
    "            if x + 1 in d:\n",
    "                _, r = d[x+1]\n",
    "            if x - 1 in d:\n",
    "                l, _ = d[x-1]\n",
    "            d[l] = [l, r]\n",
    "            d[r] = [l, r]\n",
    "            maxlen = max(maxlen, r-l+1)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        visited=set()\n",
    "        ans=0\n",
    "        for key,value in cnt.items():\n",
    "            if key not in visited:\n",
    "                tmp=1\n",
    "                num=key\n",
    "                while cnt[num+1]!=0:\n",
    "                    visited.add(num+1)\n",
    "                    tmp+=1\n",
    "                    num+=1\n",
    "                num=key\n",
    "                while cnt[num-1]!=0:\n",
    "                    visited.add(num-1)\n",
    "                    tmp+=1\n",
    "                    num-=1\n",
    "                ans=max(ans,tmp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "\n",
    "        if nums == []:\n",
    "            return 0\n",
    "\n",
    "        quchong = set(nums)\n",
    "\n",
    "        #print(quchong)\n",
    "\n",
    "        new_list = list(quchong)\n",
    "        new_list = nums\n",
    "\n",
    "        #print(new_list)\n",
    "        new_len = len(new_list)\n",
    "\n",
    "        sum_list = [1] * new_len\n",
    "\n",
    "        hash_dict = {}\n",
    "\n",
    "        for i in range(new_len):\n",
    "\n",
    "            #if hash_dict[new_list[i]]:\n",
    "                #continue\n",
    "\n",
    "            hash_dict[new_list[i]] = 1\n",
    "\n",
    "\n",
    "        for i in range(new_len):\n",
    "\n",
    "            start = new_list[i] + 1\n",
    "\n",
    "            print(hash_dict[new_list[i]])\n",
    "\n",
    "            while start in hash_dict:\n",
    "\n",
    "                if hash_dict[start] == 1:\n",
    "\n",
    "                    hash_dict[start] = 0\n",
    "\n",
    "                    sum_list[i] = sum_list[i] + 1\n",
    "\n",
    "                    start =start + 1\n",
    "\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            start = new_list[i] - 1\n",
    "\n",
    "            while start in hash_dict:\n",
    "                if hash_dict[start] == 1:\n",
    "\n",
    "                    hash_dict[start] = 0\n",
    "\n",
    "                    sum_list[i] = sum_list[i] + 1\n",
    "\n",
    "                    start =start - 1\n",
    "\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            hash_dict[start] = 0\n",
    "\n",
    "        \n",
    "        return max(sum_list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums)\n",
    "        self.nums = nums \n",
    "        self.d = {num:1 for num in nums}#每个num表示的长度\n",
    "        self.parent = {num:num for num in nums} #self.parent[num]表示num的父亲\n",
    "\n",
    "    def find(self, val):\n",
    "        while self.parent[val] != val:\n",
    "            val = self.parent[val]\n",
    "        return val \n",
    "    \n",
    "    def merge(self, val1, val2):\n",
    "        val1 = self.find(val1)\n",
    "        val2 = self.find(val2)\n",
    "        #print(self.d)\n",
    "        if val1==val2: return \n",
    "        self.parent[val2] = val1\n",
    "        self.d[val1] += self.d[val2]\n",
    "        self.d[val2] = self.d[val1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 不需要连续\n",
    "        # 并查集\n",
    "        if not nums: return 0\n",
    "        uf = UnionFind(nums)\n",
    "        for num in nums:\n",
    "            if num-1 in uf.d:\n",
    "                uf.merge(num-1, num)\n",
    "            if num+1 in uf.d:\n",
    "                uf.merge(num, num+1)\n",
    "        return max(uf.d.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        roots, sizes, ret = {}, {}, 0\n",
    "        def find(x):\n",
    "            if roots[x] == x:\n",
    "                return x\n",
    "            else:\n",
    "                roots[x] = find(roots[x])\n",
    "                return roots[x]\n",
    "        def union(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX != rootY:\n",
    "                if sizes[rootY] < sizes[rootX]:\n",
    "                    roots[rootX] = rootY\n",
    "                    sizes[rootY] = sizes[rootX] + sizes[rootY]\n",
    "                else:\n",
    "                    roots[rootY] = rootX\n",
    "                    sizes[rootX] = sizes[rootX] + sizes[rootY]\n",
    "        for num in nums:\n",
    "            roots[num] = num\n",
    "            sizes[num] = 1\n",
    "        for num in nums:\n",
    "            if num + 1 in roots and roots[num + 1] != roots[num]:\n",
    "                union(num, num + 1)\n",
    "            if num - 1 in roots and roots[num - 1] != roots[num]:\n",
    "                union(num - 1, num)\n",
    "\n",
    "        for k, v in sizes.items():\n",
    "            ret = max(v, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        def find(x):\n",
    "            if fa[x] == x: return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            a = find(x)\n",
    "            b = find(y)\n",
    "            fa[a] = b\n",
    "\n",
    "        fa = {}\n",
    "        for i in nums:\n",
    "            fa[i] = i\n",
    "        vis = set()\n",
    "        for i in nums:\n",
    "            if i - 1 in vis:\n",
    "                union(i-1, i)\n",
    "            if i + 1 in vis:\n",
    "                union(i, i+1)\n",
    "            vis.add(i)\n",
    "        res = 0\n",
    "        for i in fa:\n",
    "            res = max(res,find(i)-i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        dit = {}\n",
    "        nums = set(nums)\n",
    "        maxl, length = 0, 0\n",
    "        for num in nums:\n",
    "            if num not in dit:\n",
    "                left = dit.get(num-1,0)\n",
    "                right = dit.get(num+1,0)\n",
    "                length = left + right + 1\n",
    "\n",
    "                dit[num-left], dit[num+right] = length, length\n",
    "\n",
    "                dit[num] = length\n",
    "                maxl = max(maxl, length)\n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        st = set(nums)\n",
    "\n",
    "        res = {}\n",
    "        for num in st:\n",
    "            if num in res:\n",
    "                continue\n",
    "            for i in count(start=1):\n",
    "                if num + i in st:\n",
    "                    if num + i in res:\n",
    "                        cache = res[num + i]\n",
    "                    else:\n",
    "                        continue\n",
    "                else:\n",
    "                    cache = 0\n",
    "                for j in range(1, i + 1):\n",
    "                    res[num + i - j] = cache + j\n",
    "                break\n",
    "        \n",
    "        return max(res.values()) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return n \n",
    "        parent = {num: num for num in nums}\n",
    "        size = {num: 1 for num in nums}\n",
    "        numsSet = set()\n",
    "        for num in nums:\n",
    "            if num - 1 in numsSet:\n",
    "                self.union(parent, size, num, num - 1)\n",
    "            if num + 1 in numsSet:\n",
    "                self.union(parent, size, num, num + 1)\n",
    "            numsSet.add(num)\n",
    "        return max(size.values())\n",
    "\n",
    "    def union(self, parent, size, x, y):\n",
    "        rootX = self.find(parent, x)\n",
    "        rootY = self.find(parent, y)\n",
    "        if rootX == rootY:\n",
    "            return\n",
    "        parent[rootX] = rootY\n",
    "        size[rootY] += size[rootX]\n",
    "\n",
    "    def find(self, parent, x):\n",
    "        if x != parent[x]:\n",
    "            parent[x] = self.find(parent, parent[x])\n",
    "        return parent[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        nums_q,res = {},0\n",
    "        for num in nums:\n",
    "            left = 0 if num - 1 not in nums_q else nums_q[num-1]\n",
    "            right = 0 if num + 1 not in nums_q else nums_q[num+1]\n",
    "            count = left + right + 1\n",
    "            nums_q[num] = 1\n",
    "            nums_q[num-left] = count\n",
    "            nums_q[num+right] = count\n",
    "            res = max(res,count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFinder:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.rank = [1 for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        \n",
    "        rootX = self.find(self.root[x])\n",
    "        self.root[x] = rootX\n",
    "        return rootX\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return\n",
    "        if self.rank[rootX] >= self.rank[rootY]:\n",
    "            self.root[rootY] = rootX\n",
    "            self.rank[rootX] += 1\n",
    "        else:\n",
    "            self.root[rootX] = rootY\n",
    "            self.rank[rootY] += 1\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "\n",
    "        idx_map = {num: i for i, num in enumerate(set(nums))}\n",
    "        union_finder = UnionFinder(len(idx_map))\n",
    "\n",
    "        for num in idx_map:\n",
    "            i = idx_map[num]\n",
    "            if (num + 1) in idx_map:\n",
    "                union_finder.union(i, idx_map[num + 1])\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        counter = defaultdict(int)\n",
    "        \n",
    "        for num in idx_map:\n",
    "            i = idx_map[num]\n",
    "            counter[union_finder.find(i)] += 1\n",
    "        \n",
    "        return max(counter.values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
